package 困难;

/*
* 力扣地址：https://leetcode-cn.com/problems/insert-interval/
* 插入区间
* 给出一个无重叠的 ，按照区间起始端点排序的区间列表。
* 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
* 示例 1：
* 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
* 输出：[[1,5],[6,9]]
* 示例 2：
* 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
* 输出：[[1,2],[3,10],[12,16]]
* 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
*
* 思路：先将所有区间数组添加到list中并排序，然后在对进行判断
* */

import java.util.*;

public class demo57 {

    public static void main(String[] args) {

//        int[][] ins = {{1,3},{6,9}};
        int[][] ins = {{1,2},{3,5},{6,7},{8,10},{12,16}};
        int[] nins = {3,8};
//        int[] nins = {2,5};

        for (int[] t:insert(ins,nins))
            System.out.println(Arrays.toString(t));

//        insert(ins,nins);

    }

    public static int[][] insert(int[][] intervals, int[] newInterval) {

        List<Section> list = new ArrayList<Section>();

        for (int[] t:intervals){
            list.add(new Section(t));
        }

        list.add(new Section(newInterval));

        Collections.sort(list);

        Iterator<Section> iterator = list.iterator();

        Section se1 = iterator.next();

        while (iterator.hasNext()){
            Section se2 = iterator.next();
            if (se1.bot >= se2.top){

                if (se1.bot < se2.bot)
                    se1.bot = se2.bot;
                iterator.remove();
            }
            else
            {
                se1 = se2;
            }

        }

        int[][] rets = new int[list.size()][];

        int i = 0;
        for (Section t:list){
            int[] zt = new int[2];
            zt[0] = t.top;
            zt[1] = t.bot;

            rets[i++] = zt;
        }


        return rets;

    }

    static class Section implements Comparable<Section>{
        int top;
        int bot;

        public Section() {
        }

        public Section(int[] ins) {

            this.top = ins[0];
            this.bot = ins[1];
        }

        @Override
        public int compareTo(Section o) {
            if (this.top < o.top)
                return -1;
            else
            {
                if (this.top == o.top)
                {
                    if (this.bot > o.bot)
                        return 1;
                    else
                        return -1;
                }
                else
                {
                    return 1;
                }
            }
        }

        @Override
        public String toString() {
            return "Section{" +
                    "top=" + top +
                    ", bot=" + bot +
                    "}\n";
        }
    }


}
